﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习八月份
{
    public class Solution51
    {
        IList<IList<string>> res= new List<IList<string>>();
        public IList<IList<string>> SolveNQueens(int n)
        {
            char[][] path = new char[n][];
            for (int i = 0; i < n; i++)
            {

                path[i] = new char[n];


                for (int j = 0; j < n; j++)
                {

                    path[i][j] = '.';

                }
            }
            DFS(path, n,0);
            return res;


        }


        void DFS(char[][] path, int n,int row)
        {

            if (row == n)
            {
                //收集
                IList<string> list = new List<string>();
                for (int i = 0; i < n; i++)
                {


                    list.Add(new string(path[i]));
                }
                res.Add(list);


                    return;
            }



            for (int i = 0; i < n; i++)//第一行的位置
            {

                if (IsValid(path, row, i, n))
                {
                    path[row][i] = 'Q';

                    DFS(path, n, row + 1);
                    path[row][i] = '.';
                }
               


            }
        }

        private bool IsValid(char[][] path, int currow, int curcol, int n)
        {

            //同一列
            for(int i = 0;i < n;i++)
            {

                if (path[i][curcol] == 'Q')
                {
                    return false;
                }


            }
            //左上到右下

            for (int row = 0; row < n; row++)
            {

                if (curcol - (currow - row)>=0&& curcol - (currow - row)<n)
                {
                    if(path[row][curcol - (currow - row)] == 'Q')
                    {
                        return false;
                    }
                   
                }


            }
            //r上到左下

            for (int row = 0; row < n; row++)
            {

                if (curcol +(currow - row) >= 0 && curcol + (currow - row) < n)
                {
                    if (path[row][curcol + (currow - row)] == 'Q')
                    {
                        return false;
                    }

                }


            }
            return true;


        }
    }
}
